// 给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

// 示例 1:

// 输入: S = "loveleetcode", C = 'e'
// 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
// 说明:

// 字符串 S 的长度范围为 [1, 10000]。
// C 是一个单字符，且保证是字符串 S 里的字符。
// S 和 C 中的所有字母均为小写字母。

#include <string>
#include <vector>

using namespace std;

// 暴力搜索
class Solution1 {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.size();
        vector<int> res(n, n);
        for (int i{0}; i < n; ++i) {
            if (S[i] == C) {
                res[i] = 0;
                continue;
            }
            int j = i + 1;
            while (j < n && S[j] != C) ++j; // 找到当前字母S[i]之后的那个C
            if (j < n) res[i] = j - i;
            j = i - 1;
            while (j >= 0 && S[j] != C) --j; // 找到当前字母S[i]之前的那个C
            if (j >= 0) res[i] = min(res[i], i - j);
        }
        return res;
    }
};

// 距离场
class Solution2 {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.size();
        vector<int> res(n, n);
        for (int i{0}; i < n; ++i) {
            if (S[i] != C) continue;
            res[i] = 0;
            for (int j = i + 1; j < n && S[j] != C; ++j) {
                res[j] = min(res[j], j - i);
            }
            for (int j = i - 1; j >= 0 && S[j] != C; --j) {
                res[j] = min(res[j], i - j);
            }
        }
        return res;
    }
};

// 正反两次遍历
class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.size();
        vector<int> res(n, n);
        for (int i{0}; i < n; ++i) {
            if (S[i] == C) res[i] = 0;
            else if (i > 0) res[i] = res[i-1] + 1;
        }
        for (int i{n-2}; i >= 0; --i) {
            res[i] = min(res[i], res[i+1] + 1);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        vector<int> res(n, 0);
        // 从左往右遍历
        int c_index = -n;
        for (int i = 0; i < n; ++i) {
            if (s[i] == c) {
                c_index = i;
            } else {
                res[i] = i - c_index;
            }
        }
        // 从右往左遍历
        c_index = 2 * n;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == c) {
                c_index = i;
            } else {
                res[i] = min(res[i], c_index - i);
            }
        }
        return res;
    }
};
